import com.kiwi.nixu.common.LNode;

/**
 * 题目描述：
 * 已知两个链表head1 和head2 各自有序（如升序排列），
 * 请把它们合并成一个链表，要求合并后的链表依然有序
 */
public class J如何合并两个有序链表 {

    /**
     * 分析与解答：
     * 分别用指针head1、head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，
     * 则将head1 指向的结点归入合并后的链表中，否则将head2 指向的结点归入合并后的链表中。
     * 如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。
     * <p>
     * 由于链表按升序排列，
     * 首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；
     * 接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，
     * 如上图中的虚线所示。在实现的时候需要注意，要释放head2链表的头结点，
     */
    public static LNode constructList(int start) {
        int i = start;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        for (; i < 7; i += 2) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        return head;
    }

    public static void printList(LNode head) {
        for (LNode cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
    }

    /**
     * 合并两个升序排列的单链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static LNode merge(LNode head1, LNode head2) {
        if (head1 == null || head1.next == null) {
            return head2;
        }
        if (head2 == null || head2.next == null) {
            return head1;
        }
        LNode cur1 = head1.next;
        LNode cur2 = head2.next;
        LNode head = null;
        LNode cur = null;
        if (cur1.data > cur2.data) {
            head = head2;
            cur = cur2;
            cur2 = cur2.next;
        } else {
            head = head1;
            cur = cur1;
            cur1 = cur1.next;
        }

        //每次找链表剩余节点的最小值对应的节点连接到合并后链表的尾部
        while (cur != null && cur2 != null) {
            if (cur1.data < cur2.data) {
                cur.next = cur1;
                cur = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur = cur2;
                cur2 = cur2.next;
            }
        }
        //当遍历完一个链表后把另外一个链表剩余的节点连接到合并后的链表的后面
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        return head;
    }

    public static void main(String[] args) {
        LNode head1 = constructList(1);
        LNode head2 = constructList(2);
        System.out.println("head1:");
        printList(head1);
        System.out.println("\n head2:");
        printList(head2);
        System.out.println("\n合并后的链表");
        LNode head = merge(head1, head2);
        printList(head);
    }
}
